In software defined networks, and in policy-based fourth generation (4G) wireless communication networks, there is an increasing demand for flow-based packet processing, flow-based policy enforcement, and flow level isolation. In such networks, different roles may be applied to different packet flows. When a packet arrives at a packet processing node, the packet processing node needs to determine the appropriate rule set to apply to the packet flow. It is known to use a hash table to look up the rules to apply to a given packet flow. In general, each packet flow is associated with a unique flow identifier. The flow identifier is hashed by a hashing function to generate a hash key. The hash key is associated with one or more rules and is stored in a hash table. When a packet arrives at the packet processing node, the packet processing node extracts the flow identifier from the packet, hashes the flow identifier to obtain a search key, and uses the search key to look up the rules to apply to the packet flow.
Typically, the hash table is stored in an external memory, such as a DDR3 SDRAM. The hash-based lookup function compares the search key with each entry in the hash table until a match is found. This process may require many memory accesses, and each memory access adds to the processing delay. In a high speed packet processing node, it is generally desirable to reduce these delays as much as possible.
Various techniques are known to speed up the lookup operation on a hash table. For example, the hash table may be divided into a plurality of buckets. Each bucket comprises a plurality of hash entries forming a hash chain. Flow identifiers are assigned to buckets in a deterministic manner. Therefore, the packet processing node needs to search a single bucket to find a matching hash entry. In this case, the number of memory accesses is dependent on the link of the hash chains in each hash bucket.
Even when hash buckets are used, the packet processing node may need to access the memory multiple times to perform a lookup. Therefore, new techniques that reduce or minimize the number of memory accesses required to perform a data lookup are needed.